package cn.cxq.learning.string_matching;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 剑指offer
 * 正则表达式匹配
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：12824
 * 本题知识点： 字符串
 *  算法知识视频讲解
 * 题目描述
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 * 示例1
 * 输入
 * 复制
 * "aaa","a*a"
 * 返回值
 * 复制
 * true
 */
public class RegexMatching {

    @Test
    public void test() {
        System.out.println(match("a", "a."));
    }

    // 动态规划解题：
    // 动态规划求解问题的四个特征：
    // ①求一个问题的最优解；
    // ②整体的问题的最优解是依赖于各个子问题的最优解；
    // ③小问题之间还有相互重叠的更小的子问题；
    // ④从上往下分析问题，从下往上求解问题
    public boolean match(String str, String pattern) {

        boolean[][] dp = new boolean[str.length() + 1][pattern.length() + 1];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (j == 0) {
                    dp[i][j] = i == 0;
                } else { //对表达式和字符串的遍历是从一开始的，所以需要减一。
                    if (pattern.charAt(j - 1) == '*') {
                        // 当为*号时可以将表达式这个符号和前面一个符号当作不存在，即当前dp的值为当前字符串长度下匹配表达式长度减少二对应的结果
                        // 也可以看看表达式前面的一个字符和字符串当前下标的字符是否相同，如果相同，那么当前dp的值就是匹配式和字符串长度减一的结果
                        boolean case1 = false; //第一种情况；
                        boolean case2 = false; //第二种情况。
                        if (j >= 2) {
                            case1 = dp[i][j - 2];
                        }
                        if (i > 0 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
                            case2 |= dp[i - 1][j]; //将上述的结果取或。
                        }

                        dp[i][j] = case1 | case2;
                    } else {
                        // 如果字符串和表达式当前字符对应相等或者当前表达式的字符为'.',当前dp的结果为字符串和表达式长度减一的结果。
                        if (i > 0 && ((str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.'))) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                }
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }
}
